COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00007 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\parskip 6pt
\rm
\line{\sevenrm a08.tex[162,phy] \today\hfill}

\bigskip
\line{\bf Summation by Parts\hfill}

The technique of summation by parts is analogous to that of integration by
parts. To use integration by parts, find a factorization of the integrand,
$I=\int fg$, where $f$~gets simpler when differential and $g$~does not get
more complex when integrated. Find $h=\int g$, so $I=\int f\,dh=fh-\int h\,df$,
where $\int h\,df$ may be an easier problem.

\medskip\noindent
{\bf Examples:}
$$\eqalign{I&=\int\ln x\cdot x↑{10}\,dx\,,\quad f=\ln x\,,\quad g=x↑{10}\,,\quad
h={x↑{11}\over 11}\,;\cr
\noalign{\smallskip}
I&=\ln x\cdot {x↑{11}\over 11}-\int {x↑{11}\over 11}\,{dx\over x}\,,\cr}$$
and the integral simplifies to ${1\over 11}\int x↑{10}\,dx$.
$$\eqalign{I&=\int x\cos x\,dx\,,\quad f= x\,,\quad g=\cos x\,,\quad
h=\sin x\,;\cr
\noalign{\smallskip}
I&=x\sin x-\int\sin x\,dx=x\sin x+\cos x\,.\cr}$$

By analogy, we look for factorizations of summands, $S=\sum fg$, where
$f$~gets simpler when differenced and $g$~does not get more complex when
summed.

\medskip\noindent
{\bf Examples:}
$$S=\sum H↓i{i\choose 10}\,$$
where $H↓i$ is
$$1+{1\over 2}+{1\over 3}+\cdots +{1\over i}\,;$$
{}
$$f(i)=H↓i\,,\quad g(i)={i\choose 10}\,;\quad h(i)=\sum g=\sum↓{j=0}↑i{j\choose 10}
={i+1\choose 11}\,,$$
so
$${i\choose 10}={i+1\choose 11}-{i\choose 11}\,.$$
{}
$$\eqalign{S(N)&=\sum↓{i=0}↑N H↓i{i+1\choose 11}-\sum↓{i=0}↑N H↓i{i\choose 11}\cr
\noalign{\smallskip}
&=H↓N{N+1\choose 11}+\sum↓{i=1}↑N H↓{i-1}{i\choose 11}-\sum↓{i=0}↑N H↓i
{i\choose 11}\cr
\noalign{\smallskip}
&=H↓N{N+1\choose 11}-\sum {{i\choose 11}\over i}\cr}$$
which is readily summed.
$$S=\sum↓{0≤i≤N}i\cdot 2↑i\,,\quad f(i)=i\,,\quad g(i)=2↑i\,,\quad
h(i)=2↑{i+1}\,,\quad 2↑i=2↑{i+1}-2↑i\,.$$
{}
$$\eqalign{S&=\sum↓{1≤i≤N}i\,2↑{i+1}-\sum↓{1≤i≤N}i\,2↑i\cr
\noalign{\smallskip}
&=\sum↓{2≤i≤N+1}(i-1)2↑i-\sum↓{1≤i≤N}i\,2↑i\cr
\noalign{\smallskip}
&=-\sum↓{1≤i≤N}2↑i+N\,2↑{N+1}-0\cr
\noalign{\smallskip}
&=-\sum↓{1≤i≤N}(2↑{i+1}-2↑i)+N\,2↑{N+1}\cr
\noalign{\smallskip}
&=-2↑{N+1}+2+N\,2↑{N+1}\cr
\noalign{\smallskip}
&=(N-1)2↑{N+1}+2\,.\cr}$$

In integration by parts, likely candidates for $f$ are $\log x$ and powers
of~$x$. The analogous candidates for~$f$ in summation by parts are~$H↓x$,
factorial powers of~$x$, and ${x\choose k}$. Other possible candidates
don't get simpler, but get no worse; $e↑x$, $\sin x$, $\cos x$, for
integration, $2↑x$~and $(-1)↑x$ for summation. Candidates for~$g$ are
$x↑k$ or~$k↑x$ for integration, factorial powers of~$x$, ${x\choose k}$,
and $k↑x$ for summation.





\bigskip
\parindent0pt
\copyright 1986 Robert W. Floyd

First draft (not published)
May 2, 1986.
%revised: date;
%subsequently revised.

\bye